package ds;
import java.util.ArrayList;
import java.util.List;
import java.util.HashMap;

public class MyGraph {
    /**
     * 邻接表，adj[u]存储节点u的所有邻居节点编号
     */
    private List<Integer>[] adj;
    /**
     * 构造一个有n个节点的图
     * @param n 节点总数
     */
    public MyGraph(int n) {
        adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
    }
    /**
     * 添加一条无向边
     * @param u 节点u编号
     * @param v 节点v编号
     */
    public void addEdge(int u, int v) {
        adj[u].add(v);
        adj[v].add(u);
    }
    /**
     * 获取节点u的所有邻居节点编号
     * @param u 节点编号
     * @return 邻居节点编号列表
     */
    public List<Integer> getNeighbors(int u) {
    	return adj[u];
    }
    /**
     * 广度优先搜索，返回从startId到targetId的最短路径
     * @param startId 起点编号
     * @param targetId 终点编号
     * @return 最短路径上的节点编号列表，若不可达返回null
     */
    public List<Integer> bfs(int startId, int targetId) {
        // TODO: 待实现
        return null;
    }
} 